namespace Aurora
{
    enum Colour
    {
        RED,
        BLACK
    };
    template<class K,class V>
    struct RBTreeNode
    {
        pair<K,V> _kv;
        RBTreeNode<K,V>* _left;
        RBTreeNode<K,V>* _right;
        RBTreeNode<K,V>* _parent;
        Colour _col;
        RBTreeNode(const pair<K,V>& kv)
            :_kv(kv)
            ,_left(nullptr)
            ,_right(nullptr)
            ,_parent(nullptr)
        {}
    };
    template<class K,class V>
    class RBTree
    {
        using Node = RBTreeNode<K,V>;
    public:
        //插入
        bool Insert(const pair<K,V>& kv)
        {
            if(_root == nullptr)
            {
                _root = new Node(kv);
                _root->_col = BLACK;
                return true;
            }
            Node* cur = _root;
            Node* parent = nullptr;
            while(cur)
            {
                if(cur->_kv.first > kv.first)
                {
                    parent = cur;
                    cur = cur->_left;
                }
                else if(cur->_kv.first < kv.first)
                {
                    parent = cur;
                    cur = cur->_right;
                }
                else// if(cur->_kv.first == kv.first)
                {
                    return false;
                }
            }
            cur = new Node(kv);
            cur->_col = RED;
            if(parent->_kv.first > kv.first)
            {
                parent->_left = cur;
            }
            else if(parent->_kv.first < kv.first)
            {
                parent->_right = cur;
            }
            cur->_parent = parent;
            while(parent && parent->_col == RED)
            {
                //计算爷爷节点
                Node* grandfather = parent->_parent;
                if(grandfather->_left == parent)
                {
                    //计算叔叔节点
                    Node* uncle = grandfather->_right;
                    //如果叔叔节点存在并且还是红色,就做变色处理
                    if(uncle && uncle->_col == RED)
                    {
                        //将父亲和叔叔变黑,爷爷变红
                        parent->_col = uncle->_col = BLACK;
                        grandfather->_col = RED;
                        //继续向上处理
                        cur = grandfather;
                        parent = cur->_parent;
                    }
                    else//叔叔不存在或者叔叔存在且为黑
                    {
                        if(cur == parent->_left)
                        {
                            //单旋+变色
                            RotateR(grandfather);
                            parent->_col = BLACK;
                            grandfather->_col = RED;
                        }
                        else if(cur == parent->_right)
                        {
                            //双旋+变色
                            RotateL(parent);
                            RotateR(grandfather);
                            cur->_col = BLACK;
                            grandfather->_col = RED;
                        }
                        break;
                    }
                }
                else//右边parent,左边uncle
                {
                    Node* uncle = grandfather->_left;
                    if(uncle && uncle->_col == RED)
                    {
                        //变色
                        parent->_col = uncle->_col = BLACK;
                        grandfather->_col = RED;
                        //继续向上处理
                        cur = grandfather;
                        parent = cur->_parent;
                    }
                    else//叔叔不存在或者存在且为黑
                    {
                        if(cur == parent->_right)
                        {
                            //单旋+变色
                            RotateL(grandfather);
                            parent->_col = BLACK;
                            grandfather->_col = RED;
                        }
                        else if(cur == parent->_left)
                        {
                            //双旋+变色
                            RotateR(parent);
                            RotateL(grandfather);
                            cur->_col = BLACK;
                            grandfather->_col = RED;
                        }
                        break;
                    }
                }

            }
            _root->_col = BLACK;
            return true;
        }
        
        void InOrder()
        {
            _InOrder(_root);
        }
        size_t Size()
        {
            return _Size(_root);
        }
        size_t Hight()
        {
            return _Hight(_root);
        }
        bool Check(Node* root,size_t BlackNum,const size_t rfNum)
        {
            if(root == nullptr)
            {
                if(BlackNum != rfNum)
                {
                    cout << "出现两条路径黑色节点数量不一样" << endl;
                    //cout << root->_kv.first << endl;
                    return false;
                }
                return true;
            }
            if(root->_col == RED && root->_parent->_col == RED)
            {
                cout << "出现连续的红色节点" << endl;
                return false;
            }
            if(root->_col == BLACK)
            {
                BlackNum++;
            }
            return Check(root->_left,BlackNum,rfNum) && Check(root->_right,BlackNum,rfNum);
        }
        bool IsRBTree()
        {
            if(_root == nullptr) return true;
            if(_root->_col == RED) return false;
            size_t rfNum = 0;
            Node* cur = _root;
            while(cur)
            {
                if(cur->_col == BLACK)
                {
                    rfNum++;
                }
                cur = cur->_left;
            }
            return Check(_root,0,rfNum);
        }
        Node* Find(const K& key)
        {
            Node* cur = _root;
            while(cur)
            {
                if(cur->_kv.first > key)
                {
                    cur = cur->_left;
                }
                else if(cur->_kv.first < key)
                {
                    cur = cur->_right;
                }
                else if(cur->_kv.first == key)
                {
                    return cur;
                }
            }
            return nullptr;
        }
    protected:
        void RotateR(Node* parent)
        {
            Node* subL = parent->_left;
            Node* subLR = subL->_right;
            Node* ppNode = parent->_parent;
            parent->_left = subLR;
            subL->_right = parent;
            if(subLR)
                subLR->_parent = parent;
            parent->_parent = subL;
            if(parent == _root)
            {
                _root = subL;
                subL->_parent = nullptr;
            }
            else
            {
                if(ppNode->_left == parent)
                {
                    ppNode->_left = subL;
                }
                else if(ppNode->_right == parent)
                {
                    ppNode->_right = subL;
                }
                subL->_parent = ppNode;
            }
        }
        void RotateL(Node* parent)
        {
            Node* subR = parent->_right;
            Node* subRL = subR->_left;
            Node* ppNode = parent->_parent;
            subR->_left = parent;
            parent->_right = subRL;
            if(subRL)
                subRL->_parent = parent;
            parent->_parent = subR;
            if(_root == parent)
            {
                _root = subR;
                subR->_parent = nullptr;
            }
            else
            {
                if(ppNode->_left == parent)
                {
                    ppNode->_left = subR;
                }
                else if(ppNode->_right == parent)
                {
                    ppNode->_right = subR;
                }
                subR->_parent = ppNode;
            }
        }
        void _InOrder(Node* root)
        {
            if(root == nullptr) return;
            _InOrder(root->_left);
            cout << root->_kv.first << ":" << root->_kv.second << endl;
            _InOrder(root->_right);
        }
        size_t _Size(Node* root)
        {
            if(root == nullptr) return 0;
            return _Size(root->_left) + _Size(root->_right) + 1;
        }
        size_t _Hight(Node* root)
        {
            if(root == nullptr) return 0;
            size_t leftHight = _Hight(root->_left);
            size_t rightHight = _Hight(root->_right);
            return leftHight > rightHight ? leftHight + 1 : rightHight + 1;
        }
    private:
        Node* _root = nullptr;
    };
}
